package LinkedListSeries;

import java.util.HashSet;
import java.util.Set;

public class DetectCycleSolution_142_2 {
    /**
     * 其中第二步包含严密的数学证明 https://www.programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html#%E6%80%9D%E8%B7%AF
     *
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
        // 1、定义快慢指针，fast每次走两个结点，slow每次走一个结点
        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;

            // 2、数学公式推导：在相遇节点处，定义一个指针index1，在头结点处定一个指针index2
            // 让index1和index2同时移动，每次移动一个节点，那么他们相遇的地方就是环形入口的节点。
            if (fast == slow) {
                ListNode index1 = head;
                ListNode index2 = fast;

                while (index1 != index2) {
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null;
    }

    public ListNode detectCycle_2(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        ListNode cur = head;
        while (cur != null) {
            if (!set.add(cur)) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }
}
